\documentclass{article}

\usepackage{fullpage,amsthm}

\usepackage{graphicx} % support the \includegraphics command and options
\usepackage{array} % for better arrays (eg matrices) in maths
%\usepackage{paralist} % very flexible & customisable lists (eg. enumerate/itemize, etc.)
\usepackage{amsmath, amssymb, color, verbatim}
\usepackage{hyphenat,epsfig,subfigure,multirow}

% \usepackage[nottoc,notlof,notlot]{tocbibind} % Put the bibliography in the ToC
% \usepackage[titles]{tocloft} % Alter the style of the Table of Contents
%\usepackage[numbers]{natbib}

% \renewcommand{\cftsecfont}{\rmfamily\mdseries\upshape}
% \re newcommand{\cftsecpagefont}{\rmfamily\mdseries\upshape} % No bold!
%\usepackage[hypertexnames=false]{hyperref}
\usepackage{hyperref}

\usepackage{algorithm,algorithmic}

%\binoppenalty=10000
%\relpenalty=10000

\newcommand{\snote}[1]{\mnote{S: #1}}
\newcommand{\anote}[1]{\mnote{A: #1}}
\newcommand{\gnote}[1]{\mnote{G: #1}}
\newcommand{\vnote}[1]{\mnote{V: #1}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{conj}[theorem]{Conjecture}
\newtheorem{definition}{Definition}[section]
%\theoremstyle{definition}
\newtheorem{remark}[theorem]{Remark}

\newenvironment{proofof}[1]{\begin{proof}[of {#1}]}{\end{proof}}

\newcommand{\mypar}[1]{\smallskip \noindent {\bf {#1}.}}
\newcommand{\myparq}[1]{\smallskip \noindent {\bf {#1}}}

\DeclareMathOperator*{\argmax}{arg\,max}
%\newenvironment{proof}[1][Proof]{\begin{trivlist}
%\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
%\newenvironment{definition}[1][Definition]{\begin{trivlist}
%\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{example}[1][Example]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
% \newenvironment{remark}[1][Remark]{\begin{trivlist}
% \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}

\renewcommand{\qed}{\nobreak \ifvmode \relax \else
      \ifdim\lastskip<1.5em \hskip-\lastskip
      \hskip1.5em plus0em minus0.5em \fi \nobreak
      \vrule height0.75em width0.5em depth0.25em\fi}

\newcommand{\ie}{{\it i.e.,\ }}
\newcommand{\eg}{{\it e.g.,\ }}
\newcommand{\etal}{{\it et al.\,}}
\newcommand{\through}{,\ldots,}
\newcommand{\cala}{\mathcal A}
\newcommand{\calb}{\mathcal B}
\newcommand{\calgn}{{\mathcal G}_n}
%\newcommand{\HHH}{\mathcal H}
%\newcommand{\DDD}{\mathcal D}
%\newcommand{\XXX}{\mathcal X}
\newcommand{\cals}{\mathcal S}
%\newcommand{\RRR}{\mathcal R}
\newcommand{\eps}{\epsilon}
\newcommand{\z}{\mathrm{z}}
\newcommand{\zo}{\{0,1\}}
\newcommand{\oo}{\{+1,-1\}}
\newcommand{\inv}{^{-1}}
\def\E{\mathop{\mathbb{E}}\displaylimits}
\def\poly{\mathop{\rm{poly}}\nolimits}
\def\Lap{\mathop{\rm{Lap}}\nolimits}
\newcommand{\Cauchy}{\operatorname{Cauchy}}
\newcommand{\inr}{\in_{\mbox{\tiny R}}}


\begin{document}
\section{Partial Differential Privacy}
\subsection{Definitions}
The standard definition of differential privacy is as follows.
\begin{definition}[Differential privacy]
  An randomized algorithm $\mathcal A$ gives $\epsilon$-differential
  privacy if for all data sets $D$ and $D'$, differing in at most one row, and all $S \subseteq Range(\mathcal A)$,
  $$\Pr[\mathcal A(D) \in S] \le e^{\epsilon} \times \Pr[\mathcal A(D') \in S],$$
  where the probability is over the coin flips of $\mathcal A$. 
\end{definition}

This definition makes no distinction between different rows in the database.
However, it might happen that the algorithm $\mathcal A$ is very insensitive to some particular rows in the database.
For example, if the outcome of $\mathcal A$ doesn't depend on some particular row at all, then clearly
the outcome of the algorithm doesn't reveal any information about this row.

We characterize this phenomenon by introducing a generalization of the definition of differential privacy.
\begin{definition}[Partial differential privacy]
  A randomized algorithm $\mathcal A$ gives $\epsilon$-differential
  privacy to row $i$ in the database if for all data sets $D$ and $D'$, \textbf{differing only in row} $i$, and all $S \subseteq Range(\mathcal A)$,
  $$\Pr[\mathcal A(D) \in S] \le e^{\epsilon} \times \Pr[\mathcal A(D') \in S],$$
\end{definition}

The standard definition of global sensitivity of a function is given below.
\begin{definition}[Global sensitivity]
  For a function $f \colon D^n \rightarrow \mathcal R$ the \emph{global sensitivity} is
  $$S(f) = \max_{x, x' \colon d(x,x')=1} ||f(x) - f(x')||_1.$$
\end{definition}

We define partial sensitivity as follows:
\begin{definition}[Partial sensitivity]
  For a function $f \colon D_1 \times \dots \times D_n \rightarrow \mathcal R$ and an index $i \in \{1, \dots, n\}$ the \emph{partial sensitivity} of coordinate $i$ is
  $$S_i(f) = \max_{x, x' \colon d(x,x')=1, \mathbf{x_i \neq x'_i}} ||f(x) - f(x')||_1.$$
\end{definition}

Clearly, $S(f) = \max_i S_i(f)$.  

\subsection{Laplace mechanism for partial differential privacy}

Consider Laplace mechanism, applied to a function $f \colon D_1 \times \dots \times D_n \rightarrow \mathcal R$ and
adding noise, proportional to $S(f)/\epsilon$. It is well-known that such mechanism guarantees $\epsilon$-differential privacy.
However, for coordinates with low partial sensitivity, the guarantees are better.
\begin{claim}\label{clm:partial-privacy}
  Laplace mechanism, applied to a function $f \colon D_1 \times \dots \times D_n \rightarrow \mathcal R$, guarantees
  partial $\left(\epsilon \cdot \frac{S_i(f)}{S(f)}\right)$-differential privacy to coordinate $i$.
\end{claim}
\begin{proof}
  Straightforward generalization of [DMNS06].
\end{proof}

\subsection{Examples}

The motivation for discussion above is illustrated by the following example.
\begin{example}[Continuous release of a sum with exponential decay]
Suppose we have data that comes to us in continuous time. 
For example, we get numbers $x_i \in \{0, \dots, R\}$ at times $t_i$.
The goal is to release the sum of these numbers in some fixed moments of time in the future.
For simplicity, we assume that there is some fixed period $T$ between the releases.
It is essential, that we also assume that there is an exponential decay function, applied to the values, before releasing the statistic at time $t$.

This means that the sum at time $t$ is computed as follows: 
$$f_t(x) = \sum\limits_{x_i \colon t_i \le t} e^{-(\lambda \cdot (t - t_i))} x_i.$$
Clearly, $S(f) = R$, so we can add noise $Lap(R/\epsilon)$ to get $\epsilon$-differential privacy.
However, because of the exponential decay, the sensitivity of the function w.r.t. the data, which came
before the time $t$ is smaller than $R$. In particular, the partial sensitivity of $x_i$ is $S_i(f) = e^{-(\lambda \cdot (t - t_i))} \cdot R$.
This is why Laplace mechanism with noise $Lap(R/\epsilon)$ guarantees $\left(\epsilon \cdot e^{-(\lambda(t - t_i))}\right)$-differential privacy to an individual $i$ by Claim~\ref{clm:partial-privacy}.

If we consistently use Laplace mechanism with noise $Lap(R/\epsilon)$ to release the sum with intervals $T$, then 
we will guarantee $\left(\epsilon \cdot \frac{1}{1 - e^{-\lambda T}}\right)$-differential privacy to each individual.
For example, if $e^{-\lambda T} = 1/2$ this gives $2\epsilon$-differential privacy.
\end{example}
\end{document}